import java.util.ArrayList;
import java.util.List;

/**
 * 233. 数字 1 的个数
 * https://leetcode-cn.com/problems/number-of-digit-one/
 */
public class Solutions_233 {
    public static void main(String[] args) {
        int n1 = 13;  // output: 6
        int n2 = 12;  // output: 5
        int n3 = 123;  // output: 57
        int n4 = 108;  // output: 30

        List<Integer> inputs = new ArrayList<>();
        inputs.add(n1);
        inputs.add(n2);
        inputs.add(n3);
        inputs.add(n4);

        for (int input : inputs) {
            int result = countDigitOne(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：分别计算数值 num 每一位上 1 的数量
     * 关键点：
     * 个位数上的 1，每 10 个数有 1 个
     * 十位数上的 1，每 100 个数有 10 个，即 [10, 11, 12, 13, ..., 19]
     * 百位数上的 1，每 1000 个数有 100 个，即 [100, 101, 102, 103, ..., 199]
     * 千位数上的 1，每 10000 个数有 1000 个，即 [1000, 1001, 1002, ..., 1999]
     * ...
     * 以 123 为例
     * 个位上 1 的个数：
     * 标准部分：123 / 10 = 12 * 1 = 12 个
     * 额外部分：123 % 10 = 3，Math.min(1, 3 - 1 + 1)
     *      因为 123 > 121，所以额外的一个就是 121 个位上的 1
     *
     * 十位上 1 的个数：
     * 123 / 100 = 1 * 10 = 10 个
     * 123 % 100 = 23，Math.min(10, 23 - 10 + 1)
     *
     * 百位上 1 的个数
     * 123 / 1000 = 0 * 100 个
     * 123 % 1000 = 123，Math.min(100, 123 - 100 + 1)
     *
     * 以 108 为例
     * 个位上 1 的个数：
     * 标准部分：108 / 10 = 10 * 1 = 10 个
     * 额外部分：108 % 10 = 8，Math.min(1, 8 - 1 + 1)
     *
     * 十位上 1 的个数：
     * 108 / 100 = 1 * 10 = 10 个
     * 108 % 100 = 8，Math.min(10, 8 - 10 + 1)
     *
     * 百位上 1 的个数
     * 108 / 1000 = 0 * 100 个
     * 108 % 1000 = 108，Math.min(100, 108 - 100 + 1)
     */
    public static int countDigitOne(int n) {
        int res = 0;
        for (long i = 1; i <= n; i *= 10) {
            long divider = i * 10;
            // 标准部分（取决于前一位的大小，例如十位为 12，那么个位上最少有 12 个 1）
            long cnt = (n / divider) * i;
            // 额外部分
            long j = Math.max(n % divider - i + 1, 0);
            long remind = Math.min(j, i);
            res += cnt + remind;
        }
        return res;
    }

}
